package com.xcc.dataStructures.leetcode;

import java.util.ArrayList;

/**
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 * 例如：
 * 给定的二叉树是{3,9,20,#,#,15,7},
 * <p>
 * 3
 * 9     20
 * 15   7
 * <p>
 * 该二叉树之字形层序遍历的结果是
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * 输入
 * {1,#,2}
 * 返回值
 * [[1],[2]]
 */
public class Demo012_TreeNode4zhi {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode leftRoot = new TreeNode(9);
        TreeNode rightRoot = new TreeNode(20);
        TreeNode leftRoot1 = new TreeNode(15);
        TreeNode rightRoot1 = new TreeNode(7);
        root.left = leftRoot;
        root.right = rightRoot;
        leftRoot.left = leftRoot1;
        leftRoot.right = rightRoot1;

        Demo012_TreeNode4zhi node4zhi = new Demo012_TreeNode4zhi();
        ArrayList<ArrayList<Integer>> arrayLists = node4zhi.zigzagLevelOrder(root);
        System.out.println(arrayLists);
    }

    /**
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList <>>
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        int height = root.getHight() ;
        for (int i = 0; i < height; i++) {
            ArrayList<Integer> thisList = new ArrayList<>();
            //从左往右加
            if (i % 2 == 0) {
                addLeft(root, i, thisList);
                list.add(thisList);
            } else {
                addRight(root, i, thisList);
                list.add(thisList);
            }

        }
        return list;
    }

    /**
     * 从左往右加
     */
    public void addLeft(TreeNode node, int i, ArrayList<Integer> thisList) {
        if (i == 0) {
            thisList.add(node.val);
            return;
        }
        //加左子树
        if (node.left != null) {
            addLeft(node.left, i - 1, thisList);
        }
        //加右子树
        if (node.right != null) {
            addLeft(node.right, i - 1, thisList);
        }
    }

    /**
     * 从右往左加
     */
    public void addRight(TreeNode node, int i, ArrayList<Integer> thisList) {
        if (i == 0) {
            thisList.add(node.val);
            return;
        }
        //加右子树
        if (node.right != null) {
            addRight(node.right, i - 1, thisList);
        }
        //加左子树
        if (node.left != null) {
            addRight(node.left, i - 1, thisList);
        }
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

    public int getHight() {
        return Math.max(left == null ? 0 : left.getHight(), right == null ? 0 : right.getHight()) + 1;
    }
}

